home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / language / embedded / simulato / v2_3_mc6.tz / v2_3_mc6 / testfiles / treefnd2.asm < prev    next >
Assembly Source File  |  1994-05-02  |  16KB  |  301 lines
  1. ;
  2. ;
  3. ; Assn 3: Binary Search Tree.
  4. ; 11/18/92
  5. ;
  6. ; --------------------
  7. ;
  8. ; This program uses a binary tree implementation. It will accept user commands
  9. ; to insert an element on the tree, search the tree for an element, print the
  10. ; tree in an inorder traversal, or exit the program.  The commands are
  11. ; I - insert digit in list, S - search for element in list, P - print list,
  12. ; and E - exit.  Elements are single digit numbers (0-9).
  13. ;
  14. ; Note that this accepts one digit numbers as the data for each node of the
  15. ; tree, even though a word size of space is allocated.
  16. ;
  17. ; a6 = anchor pointer of the tree
  18. ; d7 = user data field
  19. ; d0 = user command
  20. ;
  21. ; this program uses extensive subroutine functions.
  22. ;
  23. ; --------------------
  24. ;
  25.  
  26.                 org     $1000                   ; program origin
  27.  
  28. left            equ     0                       ; offset for right node pointer
  29. data            equ     4                       ; offset for data region of node
  30. right           equ     6                       ; offset for left node pointer
  31.  
  32.                 clr.l   d7                      ; zero d7, data field
  33.                 move.l  d7,a6                   ; zero a6, anchor pointer
  34.                 move.w  #$3030,d7               ; set low d7 to two ASCII "0" chars
  35.                 jsr     ClearScreen             ; clear da screen
  36.  
  37. main            move    #prompt,a0              ; set a0 to point to prompt message
  38.                 jsr     WriteString             ; display prompt
  39.                 move.l  #userdata,a0            ; set a0 to point to storage area
  40.                 jsr     ReadString              ; get user input
  41.                 move.l  #userdata,a0            ; restore the a0 pointer
  42.                 clr.l   d0
  43. 7$              cmpi.b  #$20,(a0)               ; is this char a space?
  44.                 bne     8$                      ; yes! parse the space!
  45.                 addq    #1,a0                   ; increment a0 by 1 byte
  46.                 bra     7$                      ; parse loop repeat
  47. 8$              move.b  (a0),d0                 ; store first char in d0
  48.                 addq    #1,a0                   ; incr a0 to next byte
  49.  
  50.                 cmpi.b  #'P',d0                 ; is d0 = 'P' for PRINT?
  51.                 beq     1$                      ; YES! Skip to 1$
  52.  
  53.                 cmpi.b  #'E',d0                 ; is d0 = 'E' for EXIT?
  54.                 beq     exit                    ; YES! Exit program
  55.  
  56.                 cmpi.b  #'S',d0                 ; is d0 = 'S' for SEARCH?
  57.                 beq     2$                      ; YES! skip to 2$
  58.  
  59.                 cmpi.b  #'I',d0                 ; is d0 = 'I' for INSERT?
  60.                 beq     3$                      ; YES! Skip to 3$
  61.  
  62.                 move.l  #entryerror,a0          ; set a0 to error message
  63.                 jsr     WriteString             ; display it!
  64.                 bra     main                    ; repeat loop for user commands!
  65.  
  66. 1$              jsr     WriteEOL                ; end of line
  67.                 jsr     ClearScreen             ; go clear the screen
  68.                 jsr     PrintTree               ; go print the tree
  69.                 bra     main                    ; repeat loop for user commands
  70.  
  71. 2$              cmpi.b  #$20,(a0)               ; is this char a space?
  72.                 bne     21$                     ; no! skip ahead!
  73.                 addq    #1,a0                   ; up a0 to next char
  74.                 bra     2$                      ; parse space loop
  75. 21$             move.b  (a0),d7                 ; put only digit in low byte d7
  76.                 jsr     WriteEOL
  77.                 jsr     SearchTree              ; go search for an occurance of d7
  78.                 bra     main                    ; repeat loop for user commands
  79.  
  80. 3$              cmpi.b  #$20,(a0)               ; is this char a space?
  81.                 bne     31$                     ; no! skip to 31$
  82.                 addq    #1,a0                   ; up a0 to next char
  83.                 bra     3$                      ; do parse loop on spaces
  84. 31$             move.b  (a0),d7                 ; put only digit in lo byte d7
  85.                 jsr     WriteEOL
  86.                 jsr     InsertNode              ; go try to insert data to tree
  87.                 bra     main                    ; repeat loop for user commands
  88.  
  89. exit            move    #228,d7                 ; store exit code in d7
  90.                 trap    #14                     ; stop program execution/priv error
  91.  
  92.     NOLIST                ;No list turns of listing so you only get your code.
  93.     DC.W    0             ;Forces a Word Boundary.
  94.     Include "samples.asm" ;Includes our routines in your program.
  95.     LIST                  ;Turns listing back on for you
  96.     DC.W    0
  97.  
  98. ;
  99. ; SubRoutine GetNewNode : It calls malloc and obtains a 10 byte (defined in d0)
  100. ;       block of memory for the next node. It also zeros the pointers and the
  101. ;       data are of the new node block. a0 contains the address of the new
  102. ;       block, and is the only register changed.
  103. ;
  104.  
  105. GetNewNode      equ     *                       ; entry point for subroutine
  106.                 clr.l   d0                      ; zero d0
  107.                 move.b  #10,d0                  ; set up for 10 bytes of memory
  108.                 jsr     malloc                  ; go get 10byte block
  109.                 clr.l   right(a0)               ; clear right pointer of block
  110.                 clr.w   data(a0)                ; clear data area of block
  111.                 clr.l   left(a0)                ; clear left pointer of block
  112.                 rts                             ; return to calling code
  113.  
  114. ;
  115. ; SubRoutine InsertNode : Insert Node will parse the tree and try to place in
  116. ;       the appropriate spot the user data. If the data already exists, it
  117. ;       will tell the user as much, and then exit. Otherwise, it will tell
  118. ;       the user it successfully inserted the data.
  119. ;
  120. ;       This expects a6 to point to the anchor node of the tree,
  121. ;       d7 to contain the user data, and will not corrupt any registers,
  122. ;       with the possible exception of a6 if the tree is empty.
  123. ;
  124.  
  125. InsertNode      equ     *                       ; entry point for subroutine
  126.                 move.l  a6,a5                   ; make a working copy of the anchor pointer
  127.                 move.l  a6,d1                   ; dupe a6 to d1
  128.                 cmpi.l  #0,d1                   ; is the anchor = NIL?
  129.                 bne     1$                      ; NO! Skip ahead in code!
  130.  
  131.                 jsr     GetNewNode              ; YES! Tree empty! Get first node!
  132.                 move.w  d7,data(a0)             ; Store our value in data region of a0
  133.                 move.l  a0,a6                   ; set anchor to point to this block
  134.                 jmp     5$                      ; Exit AddNode! (done!)
  135.  
  136. 1$              move.w  data(a5),d1             ; dupe data to d1
  137.                 cmp     d7,d1                   ; test our data to current node data
  138.                 bgt     3$                      ; our data is less than! Skip ahead
  139.                 blt     4$                      ; our data is greater than! Skip ahead
  140.                                                 ; Our data is EQUAL! Do this!
  141.                 move.w  d7,source               ; store our data in source field
  142.                 move.l  #opener,a0              ; set a0 to point to opener message
  143.                 jsr     WriteString             ; go print opener text
  144.                 move.l  #dup,a0                 ; set a0 to point to duplicate data error
  145.                 jsr     WriteString             ; go display that!
  146.                 move.l  #waiting,a0             ; set a0 to point to "press a key" message
  147.                 jsr     WriteString             ; put that on the screen
  148.                 jsr     ReadChar                ; Wait for user response
  149.                 jmp     Exit_AN                 ; exit code
  150.  
  151. 3$              tst.l   left(a5)                ; can we move left in tree?
  152.                 beq     31$                     ; NO! Insert a node here! (skip ahead)
  153.                 move.l  left(a5),a5             ; Yes! We can go left! So set a5!
  154.                 jmp     1$                      ; Repeat Loop!
  155.  
  156. 31$             jsr     GetNewNode              ; Grab a new node!
  157.                 move.w  d7,data(a0)             ; store our data in node!
  158.                 move.l  a0,left(a5)             ; set this node's left pointer to our new node!
  159.                 jmp     5$                      ; jump and display inserted message!
  160.  
  161. 4$              tst.l   right(a5)               ; Can we move right in the tree?
  162.                 beq     41$                     ; NO! Insert a node here! (skip ahead)
  163.                 move.l  right(a5),a5            ; YES! We can go right! Set a5!
  164.                 jmp     1$                      ; Repeat Loop!
  165.  
  166. 41$             jsr     GetNewNode              ; Grab a new node!
  167.                 move.w  d7,data(a0)             ; store our data in node!
  168.                 move.l  a0,right(a5)            ; set this node's right pointer to our new node!
  169.  
  170. 5$              move.w  d7,source               ; store our data at source location
  171.                 move.l  #opener,a0              ; set a0 to opener message
  172.                 jsr     WriteString             ; display that!
  173.                 move.l  #inserted,a0            ; set a0 to display inserted message
  174.                 jsr     WriteString             ; display that!
  175.                 move.l  #waiting,a0             ; set a0 to point to "press a key" message
  176.                 jsr     WriteString             ; display that!
  177.                 jsr     ReadChar                ; wait for user response!
  178.  
  179. Exit_AN         rts                             ; return to calling code
  180.  
  181. ;
  182. ; SubRoutine SearchTree : This routien will search the tree for an occurance
  183. ;       of the user data. It expects a6 to be the anchor pointer, and d7 to
  184. ;       be the user data. It corrupts no registers, and displays appropriate
  185. ;       "found" or "not found" result codes on the monitor.
  186. ;
  187.  
  188. SearchTree      equ     *                       ; entry point for code
  189.                 movem.l a5,-(a7)                ; store a5, register used
  190.                 move.l  a6,a5                   ; make a5 working copy of anchor
  191.                 move.w  d7,source               ; store d7 in source field
  192.                 move.l  a6,d1                   ; dupe a6 to d1 for comp
  193.                 cmpi.l  #0,d1                   ; is tree empty?
  194.                 beq     4$                      ; yes! exit code and give error!
  195.  
  196. 1$              move.w  data(a5),d1             ; move data t od1
  197.                 cmp.w   d7,d1                   ; check our data against node data
  198.                 bgt     2$                      ; less than? YES! skip ahead!
  199.                 blt     3$                      ; greater than? YES! skip ahead!
  200.  
  201.                 move.l  #opener,a0              ; set a0 to point to opener msg
  202.                 jsr     WriteString             ; display that!
  203.                 move.l  #wasfound,a0            ; set a0 to "found" message
  204.                 jsr     WriteString             ; display that!
  205.                 move.l  #waiting,a0             ; set a0 to "press a key" msg
  206.                 jsr     WriteString             ; display that
  207.                 jsr     ReadChar                ; wait for user response
  208.                 bra     Exit_ST                 ; exit this code!
  209.  
  210. 2$              tst.l   left(a5)                ; can we go left in tree?
  211.                 beq     4$                      ; NO! Exit code and give error!
  212.                 move.l  left(a5),a5             ; set a5 to left node!
  213.                 bra     1$                      ; repeat loop!
  214.  
  215. 3$              tst.l   right(a5)               ; can we go right in tree?
  216.                 beq     4$                      ; No! Exit code and give error!
  217.                 move.l  right(a5),a5            ; set a5 to right node!
  218.                 bra     1$                      ; repeat loop!
  219.  
  220. 4$              move.l  #opener,a0              ; set a0 to opener msg
  221.                 jsr     WriteString             ; display that!
  222.                 move.l  #notfound,a0            ; set a0 to "not found" message
  223.                 jsr     WriteString             ; display that!
  224.                 move.l  #waiting,a0             ; set a0 to "press a key" message
  225.                 jsr     WriteString             ; display that!
  226.                 jsr     ReadChar                ; wait for user input
  227.                 bra     Exit_ST                 ; exit code!
  228.  
  229. Exit_ST         movem.l (a7)+,a5                ; restore a5
  230.                 rts                             ; return to calling code
  231.  
  232. ;
  233. ; SubRoutine PrintTree : This code will parse the tree and print in-order
  234. ;       traversal results of the binary tree, or an error message saying
  235. ;       the tree is empty if a6 = null. This code corrupts no registers,
  236. ;       and implements stack procedures via a7 postincr/predecr calls.
  237. ;       It only expects a6 to be the anchor pointer
  238. ;
  239.  
  240. PrintTree       equ     *                       ; entry point for code
  241.                 move.l  a6,a5                   ; make a5 working copy of anchor
  242.                 move.l  a6,d1                   ; dupe a6 to d1 for comp
  243.                 cmpi.l  #0,d1                   ; is tree empty?
  244.                 beq     4$                      ; yes! exit code and give error!
  245.  
  246.                 move.l  #0,-(a7)                ; put a null in the stack longword sized
  247.  
  248. 1$              move    data(a5),source         ; copy this node's data to disp field
  249.                 move.l  #source,a0              ; set a0 to point to disp field
  250.                 jsr     WriteString             ; display that!
  251.  
  252.                 tst.l   right(a5)               ; can we go right?
  253.                 beq     2$                      ; NO! Skip to 2$
  254.                 move.l  right(a5),-(a7)         ; push right address to stack
  255.  
  256. 2$              tst.l   left(a5)                ; can we go left?
  257.                 beq     3$                      ; No! Skip to 3$
  258.                 move.l  left(a5),a5             ; set a5 to left node
  259.                 bra     1$                      ; repeat loop!
  260.  
  261. 3$              move.l  (a7)+,a5                ; pop the next "right" address off stack
  262.                 move.l  a5,d1                   ; dupe a5 to d1
  263.                 cmpi.l  #0,d1                   ; is a5 = 0 (done) ?
  264.                 beq     Exit_PT                 ; YES! Exit this code!
  265.                 bra     1$                      ; No! repeat loop!
  266.  
  267. 4$              move.l  #emptytree,a0           ; set a0 to "empty tree" message
  268.                 jsr     WriteString             ; display that!
  269.                 move.l  #waiting,a0             ; set a0 to "press a key" message
  270.                 jsr     WriteString             ; display that!
  271.                 jsr     ReadChar                ; wait for user input
  272.  
  273. Exit_PT         jsr     WriteEOL                ; put an eol marker on screen
  274.                 rts                             ; return to calling code
  275.  
  276. ;
  277. ; User messages follow:
  278. ;
  279.  
  280. opener          dc.b    'Integer '
  281. source          ds.w    1
  282.                 dc.b    ' ',0
  283. dup             dc.b    'already exists in the tree.',13,10,0
  284. inserted        dc.b    'was inserted successfully.',13,10,0
  285. notfound        dc.b    'was not found.',13,10,0
  286. wasfound        dc.b    'was found in the tree.',13,10,0
  287. waiting         dc.b    'Press any key to continue, please...',13,10,0
  288. emptytree       dc.b    'Not possible to print tree: Tree is empty.',13,10,0
  289. prompt          dc.b    'Command? > ',0
  290. entryerror      dc.b    'Error: Unable to understand. Use "I", "S", "P", or "E".',13,10
  291.                 dc.b    '    I 5    would insert 5 into the tree;',13,10
  292.                 dc.b    '    S 5    would search for 5 in the tree;',13,10
  293.                 dc.b    '    P      would PRE-ORDER print the tree;',13,10
  294.                 dc.b    '    E      would exit this program.',13,10,13,10,0
  295. userdata        ds.w    6
  296.  
  297. ;
  298. ; now end source listing
  299. ;
  300.                 end
  301.